package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Matrix01 {

	public static void main(String[] args) {
		Matrix01 object = new Matrix01();
		List<List<Integer>> matrix = new ArrayList<>();
		List<Integer> list = new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		List<Integer> list3 = new ArrayList<>();
		List<Integer> list4 = new ArrayList<>();
		List<Integer> list5 = new ArrayList<>();
		List<Integer> list6 = new ArrayList<>();
		List<Integer> list7 = new ArrayList<>();
		List<Integer> list8 = new ArrayList<>();
		list.add(0);matrix.add(list);
		list2.add(1);matrix.add(list2);
		list3.add(1);matrix.add(list3);
		list4.add(1);matrix.add(list4);
		list5.add(1);matrix.add(list5);
		list6.add(1);matrix.add(list6);
		list7.add(1);matrix.add(list7);
		list8.add(0);matrix.add(list8);
//		matrix.add(new ArrayList<>(list));
//		matrix.add(new ArrayList<>(list2));
//		matrix.add(new ArrayList<>(list3));
		System.out.println(object.updateMatrix(matrix));
	}
	
	private static final int[][] dir = {{-1 , 0}, {1, 0}, {0, 1}, {0, -1}};
	
	//思路错了，不是动态规划，是深度优先遍历
    public List<List<Integer>> updateMatrix_2(List<List<Integer>> matrix) {
        if(matrix == null || matrix.get(0) == null){
        	return matrix;
        }
        int m = matrix.size();
        int n = matrix.get(0).size();
    	int[][] dp = new int[m][n];
    	Arrays.fill(dp, Integer.MAX_VALUE);
    	boolean find  = false;
    	int firstX = 0, firstY = 0;
    	for(int i = 0; i < m; i++){
    		for(int j = 0; j < n; j++){
    			int min = Integer.MAX_VALUE - 1;
    			if(matrix.get(i).get(j) != 0){
    				if(find){
    					for(int k = 0; k < dir.length; k++){
    						int x = i + dir[k][0];
    						int y = j + dir[k][1];
    						if(x < 0 || x >= m || y < 0 || y >= n){
    							continue;
    						}
    						if(dp[x][y] < min){
    							min = dp[x][y];
    						}
    					}
    				}
    				dp[i][j] = min + 1;
    			}else{
    				if(!find){
    					find = true;
    					firstX = i;
    					firstY = j;
    				}
    				dp[i][j] = 0;
    			}
    		}
    	}
//    	并不是到第一个发现的就是最短的，不如0 0   到 3 10  肯定比4 2要长，但是3 10是最先发现的
//    	for(int i = 0; i < firstX; i++){
//    		for(int j = 0; j < n; j++){
//    			dp[i][j] = Math.abs(firstY - j) + firstX - i;
//    		}
//    	}
//    	for(int i = firstX; i < n; i++){
//    		for(int j = 0; j < firstY; j++){
//    			if(dp[i][j] == Integer.MAX_VALUE){
//    				
//    			}
//    			dp[i][j] = Math.abs(firstY - j) + firstX - i;
//    		}
//    	}
    	
    	return matrix;
    }
    
    
    //深度优先遍历
    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
    	if(matrix == null || matrix.get(0) == null){
        	return matrix;
        }
        int m = matrix.size();
        int n = matrix.get(0).size();
        int[][] memorization = new int[m][n];
        boolean[][] find = new boolean[m][n];
        for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				memorization[i][j] = Integer.MAX_VALUE;
			}
		}
        for(int i = 0; i < m; i++){
    		for(int j = 0; j < n; j++){
    			if(matrix.get(i).get(j) != 0){
    				matrix.get(i).set(j, dfs(matrix, i, j, m , n, memorization, find));
    			}
    			
    			for (int p = 0; p < m; p++) {
    				for (int q = 0; q < n; q++) {
    					System.out.print(memorization[p][q] + " ");
    				}
    				System.out.println();
    			}
    		}
        }
        return matrix;
    }
    
    
    //这算第一次独立写dfs吧，竟然遇到了0,0 -> 1,0  然后1,0  --> 0,0最后就栈溢出
    
    //最后又遇到了这样一个问题，0 1 1 1 1 1 1 0的时候
    //第二个1是2，第三个1是3
    //当遇到第二个1，find[2][0] = true.在进行记忆化搜索的时候，第三个1由于判断第二个1在find
    //所以跳过了第二个1，导致直接向下搜索，第三个1的结果为4了
    
    //AC了, 37ms
    public int dfs(List<List<Integer>> matrix, int x, int y, int m, int n, 
    		int[][] memorization, boolean[][] find){
    	if(x < 0 || x >= m || y < 0 || y >= n){
			return 0;
		}
    	//一个可能的解决方法就是判断周围的是否有小于2的，如果有，则在搜索一遍
    	if(memorization[x][y] != Integer.MAX_VALUE){
    		for(int k = 0; k < dir.length; k++){
    			int i = x + dir[k][0];
    			int j = y + dir[k][1];
    			if(i < 0 || i >= m || j < 0 || j >= n){
    				continue;
    			}
    			if(memorization[i][j] <= memorization[x][y] - 2){
    				memorization[x][y] = memorization[i][j] + 1;
    			}
    		}
    		return memorization[x][y];
    	}
    	
    	if(matrix.get(x).get(y) == 0){
    		memorization[x][y] = 0;
    		return 0;
    	}
    	int min = Integer.MAX_VALUE;
    	find[x][y] = true;
    	for(int k = 0; k < dir.length; k++){
			int i = x + dir[k][0];
			int j = y + dir[k][1];
			if(i < 0 || i >= m || j < 0 || j >= n){
				continue;
			}
			if(matrix.get(i).get(j) == 0){
				memorization[i][j] = 0;
				memorization[x][y] = 1;
				find[x][y] = false;
				return 1;
			}
		}
    	for(int k = 0; k < dir.length; k++){
			int i = x + dir[k][0];
			int j = y + dir[k][1];
			if(i < 0 || i >= m || j < 0 || j >= n || find[i][j]){
				continue;
			}
			min = Math.min(min, dfs(matrix, i , j, m, n, memorization, find) + 1);
		}
    	find[x][y] = false;
    	memorization[x][y] = min;
    	return min;
    }
    
    
    //BFS
    public List<List<Integer>> updateMatrixBFS(List<List<Integer>> matrix) {
        int m = matrix.size();
        int n = matrix.get(0).size();
        
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix.get(i).get(j) == 0) {
                    queue.offer(new int[] {i, j});
                }
                else {
                    matrix.get(i).set(j, Integer.MAX_VALUE);
                }
            }
        }
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1) continue;
                queue.add(new int[] {r, c});
                matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
            }
        }
        
        return matrix;
    }
    
    
    //Runtime: 44 ms
    public List<List<Integer>> updateMatrixTwoSweep(List<List<Integer>> matrix) {
        List<List<Integer>> answer = new LinkedList();
		if(matrix.size() == 0) return answer;
		int[][] array = new int[matrix.size()][matrix.get(0).size()];
		int i = 0, j = 0;
		for(List<Integer> list : matrix) {
			for(Integer x : list) {
				if(x == 0) {
					array[i][j] = 0;
				}
				else {
					int left = Integer.MAX_VALUE - 1, top = Integer.MAX_VALUE - 1;
					if(i - 1 >= 0) top = array[i - 1][j];
					if(j - 1 >= 0) left = array[i][j - 1];
					array[i][j] = Math.min(Integer.MAX_VALUE - 1, Math.min(top, left) + 1);
				}
				j++;
			}
			j = 0;
			i++;
		}
		for(int k = array.length - 1; k >= 0; k--) {
			for(int m = array[0].length - 1; m >= 0; m--) {
				if(array[k][m] != 0 && array[k][m] != 1) {
					int down = Integer.MAX_VALUE - 1, right = Integer.MAX_VALUE - 1;
					if(k + 1 < array.length) down = array[k + 1][m];
					if(m + 1 < array[0].length) right = array[k][m + 1];
					array[k][m] = Math.min(array[k][m], Math.min(down, right) + 1);
				}
			}
		}
		for(int[] l : array) {
			List<Integer> tmp = new LinkedList();
			for(int n : l) {
				tmp.add(n);
			}
			answer.add(tmp);
		}
		return answer;
    }
}
 